学着zkw突然回来整理平衡树

平衡树呢,是一种比较毒瘤的数据结构,

首先,其种类非常多,实现原理也各有差异,各有千秋,

而且其应用也非常广泛,

之前看见_rqy说不会线段树然后敲了一个平衡树A掉题目

所以我将分类整理各类平衡树

说到Splay,第一次正式学习是在qbxt的晚自习,然而并没有听懂,最近回来补发现并不难

因为平衡树主要操作无非分割和旋转两类整理操作,Splay是旋转操作,

所以Splay的主要操作核心就在于交换节点之间的关系,那么懂了思路以后,就全是模拟啦...

事实上学了Splay,旋转Treap是很简单的东西

一种非常广泛的数据结构,主要的操作就是转...

Splay的操作较简单,主要是模拟,

唯一的前置知识好像就是就是二叉搜索树\(BST\)(\(binary\ search\ tree\))

具有以下特性:

显然是一棵二叉树,

每个节点有一个权值\(val\),

对于每个节点\(k\),要么其左子树为空,否则其左子树的所有元素节点权值都小于\(val[k]\),

对于其右子树,要求其中权值全部大于\(val[k]\),

如果整棵树中有几个节点权值相等,那么将这个元素对应的节点多开一个域\(sum\),表示这个权值的元素的个数

树中所有子树全是\(BST\)

这样一来,形态大致如下:

我们为什么要设立这样一个建立结构的规则呢?

显然这样非常适合数的查找,基本上就是二分的思路,无论是访问第\(k\)小值,还是访问权值为\(v\)的节点,都可以快速地实现目标,插入也是如此

具体步骤(比如找权值为\(v\)的元素):

从根节点开始寻找:

对于当前节点\(k\),如果现在\(v = val[k]\),

否则,如果当前值较小,说明目标值一定在左子树,查找左儿子,否则去查找右儿子,

重复2-3步,直到出现以下两种状况:

在查找过程中如步骤2,找到节点,完成查找,

直到找到最下方的空节点,也没有找到目标节点,说明这个节点并不存在

(查询操作一般不会这样的)

p.s. 对于插入操作,如果找到第二种情况的空节点,那么说明可以直接插入这个新节点,毕竟之前没有这个节点,新建就完了

这里注意,我们处理这些信息根本不用递归,只需要写个函数然后在函数之内跑循环就完了,这样更加高效

这就是\(BST\)处理元素的主要原理,步骤

可以发现这样类似于二分的方法是非常高效的,可以方便地维护出数列中与大小关系有关的数据

比如说:

求第\(k\)大的数的值

求大小为\(v\)的元素的排名

求比\(v\)大的最小数(后继)

求比\(v\)小的最大数(前驱)

求区间内第\(k\)大的数(并不)

注意区间求值是树套树的操作,不是\(BST\)的操作

那么在没接触Splay的情况下,我们来看一看完全不需要Splay的一些操作及函数实现:

我们一般采用动态开点的操作来进行元素插入,说的通俗就是随着用随着开

这里变量\(cnt\)就是这样一个作用,开点的时候:

rt存的是当前\(BST\)的根

\(ch[k][0/1]\)储存的是每个节点的左右儿子,\(ch[k][0]\)为左,\(ch[k][1]\)为右,

\(f[k]\)储存的则是节点父亲,\(f[rt]=0\),

\(val[k]\)存的是\(k\)节点的值,

\(size[k]\)存以节点\(k\)为根的子树的大小,

\(sum[k]\)存元素\(k\)出现的次数,就是序列中有几个值为\(val[k]\)的元素

用于更新节点信息,具体作用其实就是维护子树大小,节点的关系不改变

翻译:

这里注意这个函数的使用,\(update\)操作一定要先对子节点再对父节点,这样才能保证正确性,

因为越是深度小的节点,其信息就越是从子节点合并上来的,如果先更新父节点,父节点的信息很可能没有被"最新"子节点信息更新,反而被未更新的"老"子节点更新,在信息访问的时候会爆炸,实为下策

如果先维护子节点,那么其所有祖宗节点的更新都有了保障,因为其使用的子节点信息全部是更新过的,

主要实现思想在上面了,

代码给出,